#include "InsertionSort.h"


void
Insertion_sort_lin(int* array, int a_size)
{
	register int i = 1, j;
	int tmp;
	while (i < a_size) {
		tmp = array[i];
		j = i - 1;
		while (j >= 0 && array[j] > tmp) {
			array[j+1] = array[j];
			--j;
		}
		array[j+1] = tmp;
		++i;
	}
}



inline int
Insertion_sort_bin__get_index_binsearch(int what, int* array, int a_size)
{
	int L = 0, R = a_size, M;
	while (L < R) {
		M = (L + R) / 2;
		if (what >= array[M])
			L = M+1;
		else
			R = M;
	}
	return L;
}



void
Insertion_sort_bin(int* array, int a_size)
{
	register int i = 1, j;
	int tmp, k;
	while (i < a_size) {
		j = i - 1;
		tmp = array[i];
		k = Insertion_sort_bin__get_index_binsearch(tmp, array, i);
		while (j >= k) {
			array[j+1] = array[j];
			--j;
		}
		array[k] = tmp;
		++i;
	}
}
